package kyssion.leetcode.num1_50;

/**
 * 给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符。
 * '*' 匹配零个或多个前面的元素。
 * 匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
 * <p>
 * 说明:
 * <p>
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 * 示例 1:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 * 示例 2:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a*"
 * 输出: true
 * 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
 * 示例 3:
 * <p>
 * 输入:
 * s = "ab"
 * p = ".*"
 * 输出: true
 * 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
 * 示例 4:
 * <p>
 * 输入:
 * s = "aab"
 * p = "c*a*b"
 * 输出: true
 * 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
 * 示例 5:
 * <p>
 * 输入:
 * s = "mississippi"
 * p = "mis*is*p*."
 * 输出: false
 */
public class code10_正则表达式匹配 {

    public static void main(String[] args) {
//        test2();
        test1();
    }

    public static void test2() {
        System.out.println(new code10_正则表达式匹配().isMatch2("aab", "c*a*b"));
    }

    public static void test1() {
        System.out.println(new code10_正则表达式匹配().isMatch("", "."));
        System.out.println(new code10_正则表达式匹配().isMatch("", ".*"));
        System.out.println(new code10_正则表达式匹配().isMatch("ab", ".*c"));
        System.out.println(new code10_正则表达式匹配().isMatch("abc", ".*"));
        System.out.println(new code10_正则表达式匹配().isMatch("f", ".*x*"));
        System.out.println(new code10_正则表达式匹配().isMatch("aab", "c*a*b"));
        System.out.println(new code10_正则表达式匹配().isMatch("bbbba", ".*a*a"));
        System.out.println(new code10_正则表达式匹配().isMatch("aabcbcbcaccbcaabc", ".*a*aa*.*b*.c*.*a*"));
        System.out.println(new code10_正则表达式匹配().isMatch("aabcbcbcaccbcaabc", ".*a*"));
        System.out.println(new code10_正则表达式匹配().isMatch("abcaaaaaaabaabcabac", ".*ab.a.*a*a*.*b*b*"));
        System.out.println(new code10_正则表达式匹配().isMatch("mississippi", "mis*is*ip*."));
        System.out.println(new code10_正则表达式匹配().isMatch("abbbcbbb", "ab*"));

        System.out.println("---------------------------");
        System.out.println();
        System.out.println(new code10_正则表达式匹配().isMatch2("", "."));
        System.out.println(new code10_正则表达式匹配().isMatch2("", ".*"));
        System.out.println(new code10_正则表达式匹配().isMatch2("ab", ".*c"));
        System.out.println(new code10_正则表达式匹配().isMatch2("abc", ".*"));
        System.out.println(new code10_正则表达式匹配().isMatch2("f", ".*x*"));
        System.out.println(new code10_正则表达式匹配().isMatch2("aab", "c*a*b"));
        System.out.println(new code10_正则表达式匹配().isMatch2("bbbba", ".*a*a"));
        System.out.println(new code10_正则表达式匹配().isMatch2("aabcbcbcaccbcaabc", ".*a*aa*.*b*.c*.*a*"));
        System.out.println(new code10_正则表达式匹配().isMatch2("aabcbcbcaccbcaabc", ".*a*"));
        System.out.println(new code10_正则表达式匹配().isMatch2("abcaaaaaaabaabcabac", ".*ab.a.*a*a*.*b*b*"));
        System.out.println(new code10_正则表达式匹配().isMatch2("mississippi", "mis*is*ip*."));
        System.out.println(new code10_正则表达式匹配().isMatch2("abbbcbbb", "ab*"));
    }

    /**
     * 动态规划的写法 后面的一个匹配其实是依赖之前的匹配信息
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch2(String s, String p) {
        boolean[] canMatch = new boolean[s.length() + 1];
        canMatch[0] = true;
        char[] pchars = p.toCharArray();
        char[] schars = s.toCharArray();
        for (int pIndex = 0; pIndex < pchars.length; pIndex++) {
            if (pIndex + 1 < pchars.length && pchars[pIndex + 1] == '*') {
                for (int sIndex = 0; sIndex < schars.length; sIndex++) {
                    canMatch[sIndex + 1] = canMatch[sIndex + 1] ||
                            (canMatch[sIndex] && (pchars[pIndex] == '.' || pchars[pIndex] == schars[sIndex]));
                }
                pIndex++;
            } else {
                for (int sIndex = schars.length-1; sIndex >=0; sIndex--) {
                    canMatch[sIndex+1]=(canMatch[sIndex] && (pchars[pIndex] == '.' || pchars[pIndex] == schars[sIndex]));
                }
                canMatch[0]=false;
            }
        }
        return canMatch[s.length()];
    }

    /**
     * 模式串匹配算法 1. 递归法, 这个就是练手的递归方法其实很好懂的
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        char[] schars = (s).toCharArray();//增加一个数组位置处理结尾a*这种情况
        char[] pchars = (p).toCharArray();
        return canPans(schars, 0, pchars, 0);
    }

    /**
     * a* 表示匹配a拥有n个, . 匹配任意的字符串
     *
     * @param schars
     * @param sIndex
     * @param pchars
     * @param pIndex
     * @return
     */
    public boolean canPans(char[] schars, int sIndex, char[] pchars, int pIndex) {
        //表示模式串和匹配串已经一一匹配了
        if (sIndex >= schars.length && pIndex >= pchars.length) {
            return true;
        }
        if (pIndex >= pchars.length && sIndex < schars.length) {
            return false;
        }
        if (pIndex + 1 < pchars.length && pchars[pIndex + 1] == '*') {
            //表示a* 的时候是0个参数
            if (canPans(schars, sIndex, pchars, pIndex + 2)) {
                return true;
            } else {
                //a* 的时候穷举 a有多少个
                while (sIndex < schars.length && (schars[sIndex] == pchars[pIndex] || pchars[pIndex] == '.')) {
                    if (canPans(schars, sIndex + 1, pchars, pIndex + 2)) {
                        return true;
                    }
                    sIndex++;
                }
                return false;
            }
        } else {
            //pIndex一定保证小于pchar.length 但是 sIndex 不保证小于schar
            //a*的问题是可以匹配null 应为逻辑中首先计算的就是null
            if (sIndex < schars.length && (schars[sIndex] == pchars[pIndex] || pchars[pIndex] == '.')) {
                return canPans(schars, sIndex + 1, pchars, pIndex + 1);
            } else {
                return false;
            }
        }
    }

}